import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
    private int maxN;
    private int n;      //current number of elements on this   pq
    private int[] pq;   //pq[1..len]   occupied
    private int[] qp;   //qp[0..len-1] occupied
    private Key[] keys;

    public IndexMinPQ(int maxN) {
        if(maxN < 0) throw new IllegalArgumentException();
        this.maxN = maxN;
        n = 0;
        keys = (Key[]) new Comparable[maxN + 1];
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];
        for(int i = 0; i <= maxN ; i++)
            qp[i] = -1;
    }

    public boolean isEmpty() {
        return n == 0;
    }
    // SUOHC:use qp
    public boolean contains(int i) {
        validateIndex(i);
        return qp[i] != -1;
    }

    public int size() {
        return n;
    }

    public void insert(int i, Key key) {
        validateIndex(i);
        if(contains(i)) throw new IllegalArgumentException("index is already in the priority queue.");
        n++;
        qp[i] = n;//take the current index(inserted) as qp's index, hold the number of elements
        pq[n] = i;//take the number of elements as pq's index, hold the current index(inserted)
        keys[i] = key;
        /* n == 1, swim(1) dose nothing */
        /* n > 1, swim(n) probably dose something */
        swim(n);//!!! NOT swim(i)
    }

    public int minIndex() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    public Key minKey() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow");
        return keys[pq[1]];
    }

    public int delMin() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow");
        int min = pq[1];
        exch(1, n--);
        sink(1);
        assert min == pq[n+1];//why? 1<==>n, pn
        keys[min] = null;
        qp[min] = -1;
        pq[n+1] = -1;
        return min;

    }

    public Key keyOf(int i) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        else return keys[i];
    }
    // SUOHC:use qp
    public void changeKey(int i, Key key) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

    @Deprecated 
    public void change(int i, Key key) {
        changeKey(i,key);
    }
    // SUOHC:use qp
    /* the replacement value must be less than the replaced value */
    public void decreaceKey(int i, Key key) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if(keys[i].compareTo(key) == 0)  
            throw new IllegalArgumentException("Calling decreaseKey() with a value equal to the" +
                "key in the priority queue");
        else if(keys[i].compareTo(key) < 0)
            throw new IllegalArgumentException("Calling decreaseKey() with a value strictly" + 
                "greater than the key in the priority queue");
        keys[i] = key;
        swim(qp[i]);

    }
    // SUOHC:use qp
    public void increaceKey(int i, Key key) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if(keys[i].compareTo(key) == 0)  
            throw new IllegalArgumentException("Calling decreaseKey() with a value equal to the" +
                "key in the priority queue");
        else if(keys[i].compareTo(key) > 0)
            throw new IllegalArgumentException("Calling decreaseKey() with a value strictly" + 
                "less than the key in the priority queue");
        keys[i] = key;
        sink(qp[i]);
    }
    // SUOHC:use qp
    public void delete(int i) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
        
    }

    private boolean greater(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    }

    private void exch(int i, int j) {
        int swap;
        /* exchange pq[i] with pq[j] */
        swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        /* NOW, the index of keys[j] (the jth key in keys ) hold at pq[i] */
        /* the index of keys[i] (the ith key in keys ) hold at pq[j] */
        /* SO, direct assignment is OK. Variable 'swap' is in no need */
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    private void swim(int k) {
        while(k > 1 && greater(k/2, k)) {
            exch(k/2, k);
            k = k / 2;
        }
    }    

    private void sink(int k) {
        while(2 * k <= n){
            int j = 2 * k; 
            /* the smaller of TWO sub-node */
            if(j < n && greater(j, j+1)) j++;
            if(!greater(k, j))break;
            exch(k, j);
            k = j;
        }
    }
    private void validateIndex(int i) {
        if(i < 0) throw new IllegalArgumentException("index is negative: " + i);
        if(i >= maxN) throw new IllegalArgumentException("index >= capacity: " + i);
 
    }

    public Iterator<Integer> iterator() {return new HeapIterator(); }

    private class HeapIterator implements Iterator<Integer> {
        private IndexMinPQ<Key> copy;
        public HeapIterator() {
            copy = new IndexMinPQ<Key>(pq.length);
            for(int i = 1; i <= n; i++)
                copy.insert(pq[i], keys[pq[i]]);
        }

        public boolean hasNext() {return !copy.isEmpty();}
        public void remove() { throw new UnsupportedOperationException();}

        public Integer next() {
            if(!hasNext()) throw new NoSuchElementException();
            return copy.delMin();
        }

    }

    public static void main(String[] args) {
        String[] strings = {"it","was","the","best","of","times","it","was","the","worst"};
        IndexMinPQ<String> pq = new IndexMinPQ<>(strings.length);
        for(int i = 0; i < strings.length; i++) 
            pq.insert(i, strings[i]);
        /* 
        while(!pq.isEmpty()) {
            int i = pq.delMin();
            StdOut.println(i + " " + strings[i]);
        }
        */
        //StdOut.println("here...");
        /* 
        for(int i = 0; i < strings.length; i++) 
            pq.insert(i, strings[i]);
        */
        for(int i : pq) {
            //StdOut.println("i:" + i);
            StdOut.println(i + " " + strings[i]);
        }
        //StdOut.println("there...");
        /* 
        while(!pq.isEmpty()) {
            pq.delMin();
        }
        */
    }
}